package sword.T13;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-23 15:07:02 星期三
 */
class Solution {

    private int m;
    private int n;
    private int k;
    private boolean[][] graph;

    public int movingCount(int m, int n, int k) {
        graph = new boolean[m][n];
        this.m = m;
        this.n = n;
        this.k = k;
        return dfs(0, 0, 0, 0);
    }

    private int dfs(int x, int y, int sx, int sy) {
        if (x < 0 || x >= m || y < 0 || y >= n || sx+sy > k || graph[x][y])
            return 0;
        graph[x][y] = true;
        return 1+dfs(x+1, y, (x+1)%10==0 ? sx-8 : sx+1, sy)+dfs(x, y+1, sx, (y+1)%10==0 ? sy-8 : sy+1);
    }
}